#!/usr/bin/env python
# -*- indent-tabs-mode: nil; tab-width: 4; coding: utf-8 -*- 
# vi: set ts=4 sts=4 sw=4 set smarttab set expandtab                                     
#http://www.careercup.com/question?id=14912744
#Google interview question
""" 
You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}.           
Now we create a signature of this array by comparing every consecutive pir of elements. If they increase, write I else write D. For example for the above array, the signature would be "DDIIDI". The signature thus has a length of N-1. Now the question is given a signature, compute the lexicographically smallest permutation of [1,2,....n]. Write the below function in language of your choice.
        
vector* FindPermute(const string& signature);
"""         
import os, re, sys, getopt
from utils import *

@time_profile
def find_permute_david(signature):
    result = []
    index = 0
    length_signature = len(signature)
    while index < length_signature:
        char = signature[index]
        d_count = 0
        while char == 'D':
            d_count += 1
            index += 1
            if index >= length_signature: break
            char = signature[index]
        for j in range(0, d_count):
            result.append(index - j + 1)
        result.append(index - d_count + 1)
        index += 1
    if signature[-1] == 'I': result.append(length_signature + 1)
    return result
    
@time_profile
def find_permute_lobatt(signature):
    #print signature
    if len(signature) == 0: return [1]
    t, d = 0, 0
    result = []
    status = signature[0]
    for c in list(signature):
        if c == status: 
            if status == 'I': result.append(t + 1)
            else: d += 1
        else:
            if c == 'I':
                result.extend(list(range(t + 1, t - d, -1)))
                d = 0
            status = c
            if c == 'D':
                d = 1
        t += 1
    if status == 'I':
        result.append(t + 1)
    elif d != 0:
        result.extend(list(range(t + 1, t - d, -1)))
    return result

if __name__ == '__main__':
    try:
        opts, args = getopt.getopt(sys.argv[1:], 'd:', ['date=', 'debug'])               
        for opt, arg in opts:                                                            
            if opt in ['-d', '--date']: date = datetime.date(int(arg[:4]), int(arg[4:6]), int(arg[6:8]))
            elif opt in ['--debug']:
                debug = True
    except getopt.GetoptError, err:                                                      
        print str(err)
        print __doc__                                                                    
        sys.exit(1)
        
    from utils import *
    for i in range(0, 10):
        arr = random_arr(15, 0, 1)
        arr = "".join([e == 0 and 'I' or 'D' for e in arr])
        print arr
        david = find_permute_david(arr)
        lobatt = find_permute_lobatt(arr)
        david, lobatt = " ".join([str(e) for e in david]), " ".join([str(e) for e in lobatt])
        if david != lobatt: print david, ':', lobatt        
